The present invention concerns a digital signal coding device and method, and the corresponding decoding device and method.
The signal to be coded may be of any type. The signal is in general terms a set of data representing physical quantities. The following text will be concerned with a digital image, by way of example.
A conventional digital image is a matrix of for example 512xc3x97512 pixels coded in eight bits. Transmitting such an image over a low-speed channel requires several tens of minutes. Image compression techniques have been developed to reduce the transmission time.
Vector quantization is frequently used for image coding. Such a quantization uses a code vector dictionary, which can be a lattice, for example of the Dn type, each element of which is represented for example by its Cartesian coordinates, or by a polar representation.
In order to comply with the statistics of the data, it is preferable to represent a code vector of the lattice by its polar coordinates, namely its norm and an index representing its position on an isonorm. The norm of a vector is calculated in a conventional fashion, using a predetermined norm.
In a first aspect, in order to determine the index of a code vector, it is known that it is possible to use a table of correspondence between all the code vectors, represented in Cartesian coordinates, and their respective indices. This table of correspondence is very large, and consequently requires a large amount of memory space. In addition, the size of the table of correspondence is in general related to the maximum transmission rate of the coded data.
The present invention aims to remedy these drawbacks by providing a rapid method for determining the index of a code vector in a lattice of the Dn type.
In a second aspect, the coding of the index of a code vector is the coding of one event amongst a known group of events.
For this purpose, it is known how to code each event in a number of bits corresponding to the power of two greater than the number of events. Each event is thus coded in a unique fashion. However, this technique use a large number of bits.
Another known technique is entropic coding, for example of the Huffman type. This technique requires a large amount of calculation time and generates tables which occupy a large amount of memory space, notably when there are a large number of events to be coded.
The present invention aims to remedy these drawbacks by providing a method of coding an event included in a known group of events, which provides a more compact code.
To this end, the invention first of all proposes a method of determining an index of a code vector belonging to a predetermined lattice, characterised in that it includes the steps of:
determining a leader vector for the code vector,
seeking a permutation number between the code vector and the leader vector,
determining the index for the code vector according to the permutation number.
Correlatively, the invention proposes a device for determining an index of a code vector belonging to a predetermined lattice, characterised in that it has:
means of determining a leader vector for the code vector,
means of seeking a permutation number between the code vector and the leader vector,
means of determining the index for the code vector as a function of the permutation number.
The coding according to the invention can be implemented rapidly. It requires only a limited number of calculations, since seeking the index of a code vector is a search over a limited number of vectors.
The invention has the advantage of not requiring the use of a table of correspondence between code vectors and their respective indices, which saves on memory space and imposes no constraint on the transmission rate of the coded data.
The invention also concerns a method of coding a code vector included in a known group of vectors belonging to a predetermined lattice, the said vectors having the same norm, in the sense of a predetermined norm, characterised in that it includes the steps of:
determining a leader vector for the code vector,
seeking a permutation number between the code vector and the leader vector,
determining an index for the code vector as a function of the permutation number.
The invention applies to the coding of a set of data representing physical quantities, characterised in that it includes the steps of:
dividing the set of data into vectors, then, for each of the vectors resulting from the division,
vector quantization of the vector so as to determine a code vector belonging to a predetermined lattice,
determining a leader vector for the code vector,
seeking a permutation number between the code vector and the leader vector,
determining an index for the code vector as a function of the permutation number.
The invention then has advantages similar to those described previously.
According to a preferred characteristic, the coding method includes the steps of:
determining an area of the lattice according to the norm of the code vector,
seeking a set of leader vectors in the area,
seeking a sub-set of leader vectors having the same norm as the code vector,
calculating the sum of a respective number of permutations of the leader vectors of the sub-set which are different from the leader vector relating to the code vector, and of the permutation number between the code vector and its leader vector.
Thus the seeking of the leader vector and of the permutation number between the vector to be coded and the leader vector is effected on a reduced number of vectors.
According to a preferred characteristic, the permutation number is determined by applying the Schalkwijk method to the code vector and to the leader vector. This method can be implemented rapidly.
The coding device includes means of using the above characteristics which have advantages similar to those disclosed above.
The invention also concerns a method of decoding a code vector belonging to a predetermined lattice, whose coded form includes a norm and an index, characterised in that it includes the steps of:
determining a leader vector for the code vector,
determining a permutation number between the code vector and the leader vector, according to the index,
determining the code vector according to the permutation number.
Correlatively, the invention proposes a device for decoding a code vector belonging to a predetermined lattice, whose coded form includes a norm and an index, characterised in that it has:
means of determining a leader vector for the code vector,
means of determining a permutation number between the code vector and the leader vector, according to the index,
means of determining the code vector according to the permutation number.
According to a preferred characteristic, the decoding method includes the step of determining an area of the lattice as a function of the norm of the code vector, and the leader vector is sought in this area.
According to another preferred characteristic, the code vector is determined by applying the inverse Schalkwijk method to the permutation number and to the leader vector.
The decoding can be implemented rapidly, since there also searches are carried out on a limited number of vectors.
The decoding method and device make it possible to find the code vectors, for example in a receiving apparatus corresponding to a sending apparatus in which the signal was coded according to the invention.
In the second aspect, the invention proposes a method of coding an event included in a known group of events, characterised in that it includes the steps of:
determining a first number and a second number of bits which can be used to code an event, as a function of the number of events in the group,
coding the event by using the first number of bits or the second number of bits according to a selection criterion.
Correlatively, the invention proposes a device for coding an event included in a known group of events, characterised in that it has:
means of determining a first number and a second number of bits which can be used for coding an event, as a function of the number of events in the group,
means of coding the event by using the first number of bits or the second number of bits according to a selection criterion.
The method and device generate a code of variable length, whose decoding is unique. The code of variable length is more compact than a code based on the powers of two.
In addition, the coding and decoding can be implemented rapidly, since they entail only simple calculations. In particular, the invention requires no table to be stored, unlike Huffman coding.
The invention applies more particularly to the coding of a code vector included in a known group of code vectors. The method then includes the steps of:
determining a first number and a second number of bits which can be used for coding a code vector, according to the number of vectors in the group,
coding the code vector by using the first number of bits or the second number of bits according to a selection criterion.
An index is then associated with the code vector, for example to represent its position on an isonorm, or its ranking in a dictionary.
The invention also concerns a method of coding a set of data representing physical quantities, characterised in that it includes the steps of:
dividing the set of data into vectors, then, for each of the vectors resulting from the division,
vector quantization of the vector, using a known set of code vectors,
determining a group of code vectors to which the code vector used for quantizing the vector belongs,
determining a first number and a second number of bits which can be used for coding the code vector, according to the number of code vectors belonging to the group,
coding the code vector using the first number of bits or the second number of bits according to a selection criterion.
By virtue of the invention, the compression rate expressed in bits per symbol is close to entropy.
According to preferred characteristics, the determination of the first number of bits includes the calculation of the logarithm to the base 2 of the number of events in the group, and the determination of the second number of bits includes the calculation of the logarithm to the base 2 of the number of events of the group increased by one unit. The length of the codes used is thus directly related to the number of events to be coded and is simple and rapid to determine.
According to another preferred characteristic, the selection of the first number of bits or of the second number of bits includes the steps of:
allocating an integer index to the event,
determining a delimiter,
comparing the index with the delimiter, in order to select the first number of bits or the second number of bits according to the result of the comparison.
Selection of the first or second number of bits is very rapid since it entails only simple calculations.
When the selection is made, the invention includes the steps of:
coding the index decreased by half the delimiter, using the first number of bits, if the index is greater than or equal to the delimiter,
coding the index using the second number of bits, if the index is less than the delimiter.
The coding proper of the index is thus very rapid.
According to another preferred characteristic, the delimiter depends on the number of events contained in the group.
In another aspect, the invention concerns a method of decoding an event included in a known group of events, the said event being coded using a first or a second number of bits, the second number being greater than the first number, characterised in that it includes the steps of:
reading the first number of bits,
comparing the value read with a delimiter, in order to determine whether the event is coded using the first or the second number of bits.
Correlatively, the invention proposes a device for decoding an event included in a known group of events, the said event be coded using a first or a second number of bits, the second number being greater than the first number, characterised in that it has:
means of reading the first number of bits,
means of comparing the value read with a delimiter, in order to determine whether the event is coded using the first or the second number of bits.
The decoding method and device make it possible to find the index representing the coded event very simply. As already stated, the event can be a code vector.
The present invention also concerns a data processing device, a communication device, such as computer, printer or facsimile apparatus, including the preceding coding and decoding device.
The present invention also concerns a storage medium, such as a floppy disk or a CD-ROM.
The advantages of these devices and storage medium are similar to those previously described.